package com.tingyuge.base.structrue.unio;

/**
 * @Created by xiaodao
 */
public class UnionFind2 implements UnionFind
{

    private int[] parent;

    /**0 1 2 3 4 5 6 7 8 9 10
     * 0 1 2 3 4 5 6 7 8 9 10
     * 初始化的时候,这个并查集指向自己
     * @param size
     */
    public UnionFind2(int size){
        parent = new int[size];

        for (int i = 0; i <size ; i++) {
            parent[i] = i;

        }

    }

    @Override
    public int getSize() {
        return parent.length;
    }

    @Override
    public boolean isConnected(int p, int q) {
        return find(p) == find(q);
    }

    /**
     * 合并操作 复杂度为 O(h) h为树的深度
     * 考虑size 让节点小的那颗树指向节点深的那棵树,这样可以省略
     * @param p
     * @param q
     */
    @Override
    public void unionElements(int p, int q) {
        int proot = find(p);
        int qroot = find(q);
        if(proot == qroot){
            return;
        }else{
            //
            parent[proot] = qroot;
        }

    }

    //找自己的父节点
    private int find(int p){
        if(p <0 || p >= parent.length){
            throw  new IllegalArgumentException("p not exist");
        }
        //如果== 就是自己的父节点
        while (p !=parent[p]){
            p = parent[p];
        }
        return p;
    }

    public static void main(String[] args) {
        UnionFind2 un = new UnionFind2(10);
       int a =  un.find(2);
        System.out.println(a);
        System.out.println(un.parent[2]);
    }
}
